package InterviewTest.q0108_setZeroes;

public class Solution {
    /*
    如果用朴素的方法，可以遍历后记录有哪些行或者列有零 并记录 然后在遍历一边对应的置零
    但是要降低空间复杂度 则需要有效的利用当前矩阵
    我们将第一列和行作为一个用来记录的列
    然后遍历所有元素 如果有0 则将对应的列头和行头置为0 这样的方法会导致如果第一列本来就有0 就无法进行置换
    所以第一列需要一个flag 在遍历时记录是否本来就有零
    并且最后置换时 要从最后一行开始置换
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) flagCol0 = true;
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }



        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;

            }
            if (flagCol0) matrix[i][0] = 0;
        }



    }
}
